#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>



struct global_node {
	int value;
	struct global_node *next;
	struct global_node *new_node;
        };

/* _____________________________________________________________________________________________________________________*/


struct global_node *add_number(struct global_node *list, int num)
{	
      			
	struct global_node *new_node;
	
	
	new_node = malloc(sizeof(struct global_node));
	new_node->value = num;
	new_node->next = list;
	
}

/* _____________________________________________________________________________________________________________________*/


struct global_node *display(struct global_node *list)
{		
	printf("The list is \n");
	
	printf("[\t");
	while (list != NULL) {
		printf("%d\t", list->value);
		list = list->next;
	}
        printf("]");
}


/* _____________________________________________________________________________________________________________________*/

struct global_node *reverse(struct global_node *list)
{				

	struct global_node *previous = NULL, *current, *reverse = NULL;
	
	previous = malloc(sizeof(struct global_node));
	current = malloc(sizeof(struct global_node));
	
	current->value = list->value;
	current->next = NULL;
	previous = current;
	list = list->next;
	
	while (list != NULL) {
		reverse = malloc(sizeof(struct global_node));
		reverse->value = list->value;
		reverse->next = previous;
		previous = reverse;
		list = list->next;

	}
	return reverse;

}

/* _____________________________________________________________________________________________________________________*/


/* _____________________________________________________________________________________________________________________*/

struct global_node *extend(struct global_node *list)
{			
	struct global_node *temp_new_node, *new_node;
	int number, num, i;
	
	
	new_node = list;
	
	printf("Enter the number of elements you want to be there in the new list\t");
	scanf("%d", &number);

	while (new_node->next != NULL) {
		new_node = new_node->next;
	}
	for (i = 0; i < number; i++) {
		
		printf("Enter the element\t");
		scanf("%d", &num);
		
		temp_new_node = malloc(sizeof(struct global_node));
		temp_new_node->value = num;
		temp_new_node->next = NULL;
		
		new_node->next = temp_new_node;
		new_node = new_node->next;
		reverse(new_node);
	}
	return list;
}

/* _____________________________________________________________________________________________________________________*/


struct global_node *count (struct global_node *list)
{	
	int count = 0, number;
	printf("Enter the number whose frequency you want to find in the list \t");
	scanf("%d", &number);
	
	while (list != NULL) {
		if (number == list->value) {
			count++;
		}
		list = list->next;
	}
	printf("Total number of occurences of %d is %d \n", number, count);
}

/* _____________________________________________________________________________________________________________________*/

struct global_node *remove_func(struct global_node *list)
{				
	int number;
	struct global_node *current, *previous;
	
	printf("enter the element you want to deleted:\t");
	scanf("%d", &number);
	
	for (current = list, previous = NULL; current != NULL && (current->value) != number;previous = current, current = current->next) ;
	        if (previous == NULL) {
		list = list->next;
		return list;
	        } 
	
	        else {
		previous->next = current->next;
		free(current);
		return list;
	}
}


/* _____________________________________________________________________________________________________________________*/

struct node *insert(struct global_node *list)
{				
	int append_value, index, j;
	struct global_node *new_node, *p;
	
	
	printf("Enter the index at which you want to insert an element and then the value of the element with a comma in between\t");
	scanf("%d,%d", &index,&append_value);
	
	new_node = malloc(sizeof(struct global_node));
	p = list;
	
	if(index==0)
         {      new_node->value=append_value;
                new_node->next=p;
                }    
		
		else{for (;; p = p->next) {
			if (j == (index )) {
				new_node->value = append_value;
				new_node->next = p->next;
				p->next = new_node;
				break;
			}
			j++;
		}}
                        //return list;
}

/* _____________________________________________________________________________________________________________________*/

struct global_node *indexx(struct global_node *list)
{		


        int number, count = 0;	
	
	printf("Enter a number \t");
	scanf("%d", &number);
	
	while ((list->next) != NULL) {
		if (number == (list->value)) {
			break;
		}
		list = list->next;
		count++;
	}
        printf("The index of first occurence of %d is at %d",number, count);
}

/* _____________________________________________________________________________________________________________________*/


int pop(struct global_node *list)
{				
        printf("..............");
	int i, number, x;
	struct global_node *current, *previous;
	
	printf("Enter index of the number you want to\n");
	scanf("%d", &number);
	
	current = list;
	previous = NULL;
	
	for (i = 1; i < number; i++) {
			previous = current;
			current = current->next;
		}

	if (previous == NULL)
		list = current->next;
	else
		previous->next = current->next;
	x = current->value;
	free(current);
                
          
	return x;
		
		}
		



/* _____________________________________________________________________________________________________________________*/

//  I utilized all available help on the net for this function  , After creating and trying lot of functions i am using the sort used in this reference http://www.go4expert.com/forums/showthread.php?t=4593 



struct global_node *sort(struct global_node *list)
{

	struct global_node *temp1 = NULL,*temp2 = NULL,*temp3 = NULL,*temp4 = NULL,*main_temp= NULL;


	while (temp4 != list->next) {
		
		temp3 = temp1 = list;
		temp2 = temp1->next;

		while (temp1 != temp4) {

			if (temp1->value > temp2->value) {
				if (temp1 == list) {
					main_temp = temp2->next;
					temp2->next = temp1;
					temp1->next = main_temp;
					list = temp2;
					temp3 = temp2;

				} 
				else {
                			main_temp = temp2->next;
					main_temp->next = temp1;
					temp1->next = main_temp;
					temp3->next = temp2;
					temp3 = temp2;
				}

			} 
			else {
				temp3 = temp1;
				temp1 = temp1->next;
			}

			temp2 = temp1->next;
		if (temp2 == temp4)
		temp4 = temp1;

		}
		return list;

	}
	
}

/* _____________________________________________________________________________________________________________________*/

void main()
{
	int number, num, i, option, l,q;
	struct global_node  *new_node, *list, *first_node = NULL;

	
	new_node = malloc(sizeof(struct global_node));
	printf("How many elements do you want to enter in the list\t");
	scanf("%d", &number);

	for (i = 0; i < number; i++) {
		printf("Enter the element\t ");
		scanf("%d", &num);
		first_node = add_number(first_node, num);
		list = first_node;
	}

	display(list);
        printf("\n");
        
        
	while (1) {
	        printf("\nWelcome to python list implementation by link list \n");
                printf("\n");
		printf("1 Count\n");
		printf("2 Pop\n");
		printf("3 Reverse\n");
		printf("4 Remove\n");
		printf("5 Sort \n");
		printf("6 Append\n");
		printf("7 Extend\n");
		printf("8 Insert\n");
		printf("9 Index\n");
		printf("10 Display\n");
		printf("11 Exit\n");
                printf("\n");
                printf("\n");
                
                
		printf("Which option do you want to implement \t");
		scanf("%d", &option);

		switch (option) {

		case 1:
			count(first_node);
			printf("\n");
			break;
		case 2:
			l=pop(first_node);
			printf("\n");
			break;
		case 3:
			list = reverse(first_node);
			printf("\n");
			display(list);
			break;
		case 4:
			list = remove_func(first_node);
			display(list);
			printf("\n");
			break;
		case 5:
			list = sort(first_node);
			display(list);
			printf("\n");
			break;
		case 6:
			printf("Enter a number\n");
			scanf("%d",&q);
			
			list = add_number(list,q);
			display(list);
			printf("\n");
			break;
		case 7:
			list = extend(first_node);
			display(list);
			printf("\n");
			break;
		case 8:
			list = insert(first_node);
			display(list);
			printf("\n");
			break;
		case 9:
			indexx(first_node);
			printf("\n");
			break;
		case 10:
			display(list);
			printf("\n");
			break;
		case 11:
			exit(0);
		
		
		}
	}

}

/* _____________________________________________________________________________________________________________________*/
